Transformée de Walsh

Un article de Wikipédia, l'encyclopédie libre.

En mathématiques, et plus précisément en analyse harmonique, la transformée de Walsh est l'analogue de la transformée de Fourier discrète.

Elle opère sur un corps fini à la place des nombres complexes.

Elle est utilisée en théorie de l'information à la fois pour les codes linéaires et la cryptographie.

Définition[modifier | modifier le code]

Soit G un groupe abélien fini d'ordre g et d'exposant une puissance n-ième d'un nombre premier p, Fpn le corps fini de cardinal pn, χ un caractère à valeur dans Fpn et f une fonction de G dans Fpn. La transformée de Walsh est une fonction, souvent notée de l'ensemble des caractères de G dans le corps Fpn définie par :[réf. nécessaire]

.

Analyse harmonique sur un groupe abélien fini[modifier | modifier le code]

Le contexte est identique à celui de l'analyse harmonique classique d'un groupe abélien fini. La forme bilinéaire associée à l'algèbre du groupe est alors la suivante :

L'ensemble des résultats de la théorie de l'analyse harmonique s'applique, on dispose ainsi de l'égalité de Parseval, du théorème de Plancherel, d'un produit de convolution, de la dualité de Pontryagin ou encore de la formule sommatoire de Poisson.

Cas d'un espace vectoriel fini[modifier | modifier le code]

Il existe un cas particulier, celui ou le groupe G est le groupe additif d'un espace vectoriel fini. Un cas particulier est celui ou G est un corps.

La transformation discrète de Fourier est donnée par

La transformation théorique de nombre[Quoi ?] opère sur une suite de n nombres, modulo un nombre premier p de la forme , où peut être tout nombre entier positif.

Le nombre est remplacé par un nombre est une racine primitive de p, un nombre où le plus petit nombre entier positif est . Il devrait y avoir une quantité d' qui satisfassent à cette condition. Les deux nombres et élevés à la puissance n sont égaux à 1 (mod p), toutes les puissances inférieures différentes de 1.

La transformation théorique de nombre est donnée par

Une preuve de la formule d'inversion[modifier | modifier le code]

La transformation inverse est donnée par

, l'inverse de , et , l'inverse de n. (mod p)

On vérifie que cette formule donne bien l'inverse car vaut n pour z=1 et 0 pour tous les autres valeurs de z vérifiant . En effet, on a la relation (qui devrait fonctionner dans toute algèbre à division)

Soit, pour une racine -ème de l'unité

Un corps étant intègre, un des facteurs (au moins) de ce produit est nul. Donc, soit et trivialement . Soit et nécessairement .

Nous pouvons maintenant compléter la démonstration. Nous prenons la transformation inverse de la transformation.

(puisque )

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Lien externe[modifier | modifier le code]

(en) Mikko Tommila, « Number theoretic transforms »,

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Number-theoretic transform » (voir la liste des auteurs).